package leedcode_path.treeNoDE;

public class 二叉搜索树的删除 {
    /*
    * 如题，我先想的是中序遍历，然后用数组记录下来，后来发现null记录不了，可恶！！
    * 之后看完视频，分为5种情况：
    * 1.没找到，返回null
    * 2。左右都为空，为叶子节点，返回null到上一层，上一层有节点接着
    * 3，左空右不为空，直接返回右边
    * 4，左不空右为空，直接返回左边
    * 5.左右都不为空，把左孩子放在右边的最左边，然后返回右孩子
    * */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root==null) return null;
        if (root.val==key){
            if (root.left==null&&root.right==null){
                return null;
            }else if (root.left!=null&&root.right==null) {
                return root.left;
            }else if(root.left==null&&root.right!=null){
                return root.right;
            }else {
                TreeNode cur=root.right;
                while (cur.left!=null) cur=cur.left;
                cur.left=root.left;
                return root.right;
            }
        }

        if (root.val>key) root.left=deleteNode(root.left,key);
        if (root.val<key) root.right=deleteNode(root.right,key);

        return  root;

    }
}
